class Node():
    def __init__(self,value):
        self.value = value
        self.pre = None
        self.next = None

class double_link_list():
    '''双链表结构'''

    def __init__(self,node=None):
        
        self.__head = node

    def is_emply(self):

        return self.__head is None

    # '''双向链表的长度'''    
    def length(self):
        self.count = 0
        cur = self.__head
        while cur != None:
            cur = cur.next
            self.count += 1
        
        # print(self.count)
        return self.count
        
    def append(self,value):

        node = Node(value)
        
        cur = self.__head
        if self.is_emply():
            self.__head = node
        else:
            while cur.next != None:
                cur = cur.next
            cur.next =node
            node.pre = cur
        return 
    
    def add(self,value):
        node = Node(value)
        if self.is_emply():
            self.__head = node
        else:
            node.next = self.__head
            self.__head.pre = node
            self.__head = node

    def trave(self):

        cur =self.__head
        while cur != None:
            print(cur.value,end="")
            cur = cur.next
        print()
        return 
    def insert(self,index,value):
        
        if index > self.length():
            self.append(value)
        elif index < 1:
            self.add(value)
        else:
            ind = 1
            cur = self.__head
            node = Node(value)
            if ind < (index-1):
                ind += 0
                cur = cur.next
            node.next = cur.next
            node.pre = cur
            cur.next.pre = node
            cur.next = node

            
    def delete(self,value):

        cur = self.__head
        if self.is_emply():
            return 
        else:
            while cur != None:
                
                if cur.value == value:
                    cur.pre.next = cur.next
                    cur.next.pre = cur.pre
                    return 
                cur = cur.next

    def search(self,value):
        cur = self.__head
        while cur != None:
            if cur.value == value:
                return True
            cur = cur.next
        return False

if  __name__=="__main__":

    link = double_link_list()
    print(link.is_emply())
    link.append(1)
    link.append(2)
    link.append(3)
    link.append(4)
    link.append(5)
    link.add(6)
    link.trave()
    link.insert(3,9)
    link.insert(3,9)
    link.trave()
    link.delete(9)
    print(link.search(9))
    link.trave()
    print(link.length())
